The present invention relates to a process of sorting items comprising physical tokens, electronic data, or other symbols representing such tokens.
In particular, the invention relates to a method and to software for sorting mail or similar items that are themselves to be ordered (e.g., envelopes, cards, other flats, inventory items, chemical samples, or machine parts), or for sorting items that symbolically represent any other possible referents to be sorted (i.e., some useful code or index, such as the postal zip code; employed for achieving a tangible result, e.g., sorted mail).
There is no known prior art pertaining to the present inventive process.
All previously known sorting procedures that involve comparing items a fixed number of times asymptotically approach an ideal of N lg N comparisons known as the information theoretic lower bound.
In contrast, the maximum number of comparisons the present invention requires is always less than the minimum number of comparisons necessary to complete a sorting process by any of such preceding means, regardless of input ordering or the number of items; hence, greater than one (1) bit of information is gleaned from successive comparisons made via the invention's operation, thus the rate of information growth accelerates with iteration.
As a consequence, the advantage afforded by the invention grows larger as the number of items to sort grows larger.
Interpolation is commonly used to determine values between established X-axis values when a function y=ƒ(x), having only discrete values, is approximated via polynomial expressions.
A related problem is that of taking function values at lattice points as “exact” within some confidence intervals of accuracy, in order to manage the “roughening” effect of differentiation.
When using a difference procedure to enable such approximations, a finite set of discrete points is treated as analogous to a plane.
The Laplace operator based on a square lattice incorporates five-point “molecules,” wherein the boundary conditions for a specially selected position are the lattice lines and the boundary values are given at the boundary points of the lattice.
The invention makes use of similar “molecules” to locate the most central positions in spatial arrays of placed items; hence, the inventive process is understood as one that makes use of “topological interpolation.”
In order to sort items, the present invention introduces a novel interpretation of plural axes defining a spatial array and a novel use for the elements of said spatial array.
Many methods and systems for sorting electronic data or other symbols using computer systems, comprising hardware and software, are known.
Sorting is used to collect similar items, to efficiently match lists of items and to facilitate the retrieval of information.
Sorting is at the heart of prioritizing queues, bringing order to haphazardly collected data, comparing quantities, optimizing routes, managing large databases, and other embodiments that are useful and pervasive in our complex society.
Knuth in The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd Edition, 1998, estimated that in some computer installations as much as 50% of computer run time was consumed by sorting tasks.
Some examples of sorting processes in computerized applications are described in the following U.S. patents:
U.S. Pat. No. 2,984,822 issued on May 16, 1961 to Armstrong et al describes a system for comparing and sorting character data and an apparatus for directing character data stored in two record blocks to appropriate high and low lines as determined by the relative magnitude of the character data, and the compare-sort units can then be used in cascade.
U.S. Pat. No. 3,029,413 issued on Apr. 10, 1962 to O'Conner et al describes electronic switching circuits and magnetic storage means used to sort randomly arranged information according to a desired sequence.
U.S. Pat. No. 3,273,127 issued on Sep. 13, 1966 to Armstrong describes a digital sorting system and a network capable of comparing the identifying multi-bit binary signal of the record about to be fed into the system with the identifying numbers of the sequenced records already in the system, and the sorting network also rearranges the new record with respect to the previously sequenced records so that the new record may be sorted into its proper place in the sequence.
U.S. Pat. No. 3,418,632 issued on Dec. 24, 1968 to Batcher describes basic merging components used in substantially equally divided subdivisions to effect a merge of two sequences of data each arranged in ascending order, and the resultant output is automatically integrated into a single arranged sequence.
U.S. Pat. No. 3,685,024 issued on Aug. 15, 1972 to O'Conner describes a plurality of sorting switches used to perform a satisfactory partial sort when target positions change slowly, relative to the frequency of sorting.
U.S. Pat. No. 4,445,171 issued on Apr. 24, 1984 to Neches describes a multiprocessor system that sorts data content messages having a common priority in order to distribute them to processors consistent with a total network delay time and routing is determined by local acceptance or rejection of the messages at the processors, based upon destination data in the messages.
U.S. Pat. No. 4,510,567 issued on Apr. 9, 1985 to Chang et al describes a method of sorting data on a disk file by transferring records to a sort buffer, on the basis of rank, according to qualifying criteria.
U.S. Pat. No. 4,628,483 issued on Dec. 9, 1986 to Nelson describes a sorting network that simultaneously uses multiple comparators to sort the keys of N records.
U.S. Pat. No. 4,693,373 issued on Sep. 15, 1987 to Lamb et al describes a computer-controlled sorter, loader and archiving system for slides that relies on accession numbers and sorting logic to direct slides to appropriate bins or compartments.
Some examples of reducing search spaces during data processing are described in the following U.S. patents:
U.S. Pat. No. 6,385,765 issued on May 7, 2002 to Cleaveland et al describes software and methods of using a computer for specifying and verifying synchronous and asynchronous systems and that further uses a “new kind of partial-order reduction method.”
U.S. Pat. No. 6,513,031 issued on Jan. 23, 2003 to Fries et al describes a method of aiding searches in a computer environment by selecting a search area based upon accessing a user profile and upon the search query.
U.S. Pat. No. 6,523,030 issued on Feb. 18, 2003 to Horowitz describes a method for operating a computer system to minimize the number of disk storage access operations required for creating the inverted database from a series of inverted databases; and the database is divided into several smaller databases, then postings lists created for each subdatabase are sorted and common and non-common terms are merged.
Many methods and machines for sorting articles are known.
Modern item sorting practice, especially sorting practice for items of mail, is based on the use of sorting machines.
Some examples of apparatus and methods for mail sorting are described in the following U.S. patents:
U.S. Pat. No. 4,247,008 issued on Jan. 27, 1981 to Dobbs describes a microprocessor implemented method and system for use in a mail sorting machine that also compiles a list of zip codes from each envelope that moves through the machine.
U.S. Pat. No. 5,667,078 issued on Sep. 16, 1997 to Walach describes an apparatus and method for mail sorting, including:
1) generating a first sequence number for each subset of mail;
2) sorting the first subset into batches according to the first sequence number;
3) associating one of the first sequence numbers corresponding to the destination addresses of the mail items in the first subset into batches, according to the second and first sequence numbers, while disregarding N of the most significant digits of the first sequence number;
4) interleaving the batches from the first and the second subset; and
5) sorting according to the N most significant digits of the first sequence number, and the method is intended to allow porting of the mail to begin prior to all the mail being physically present at the sorter.
U.S. Pat. No. 6,073,060 issued on Jun. 6, 2000 to Robinson describes a sorting station that translates scanned signals into internal addresses that correspond to bins and the bins correspond to postal routes.
U.S. Pat. No. 6,259,964 issued on Jul. 10, 2001 to Robinson describes a sorting station that translates scanned signals into internal addresses that correspond to bins.
U.S. Pat. No. 6,274,836 issued on Aug. 14, 2001 to Walach describes a sorting machine with multiple input bins associated with multiple output bins that allows the subsequent grouping of sorted articles for resorting; thus, the first and second portions of a sorting key may be disjoint.
All of the references cited herein rely on well-known methods for sorting and do not partake of the novel processes introduced by the invention.
Although the inventive process makes use of certain techniques similar to those well known in the art of sorting items, it also departs significantly from all known methods, software, and systems that precede it.
Since the inventive process is substantively unlike known conventional methods for sorting, it thereby yields distinct, useful and tangible advantages.
Other methods used for sorting items rely on comparisons of all items to all others, on arbitrarily reducing the field for comparisons, or on a logarithmically basal index assigned to each item.
Unlike these, the present invention reduces the fields for comparisons made based on simple differences among prioritized values assigned to the items compared.
This results in significant advantages on all measures of performance (i.e., the number of required comparisons, the number of required moves, and the time necessary to complete processing when the number of items to sort is not insignificantly small).
Although the invention includes features similar to methods belonging to the general category of an insertion sort, it is novel since the way items are placed defies the limits of the information theoretic lower bound.
Unlike an exchange sort, items sorted via the inventive process are never found to be out of order and so are not interchanged.
Continuous movement of items, as required by an exchange sort, is not necessary while items are being sorted.
Unlike a selection sort, items are not repeatedly searched for those next in order during item placement.
Unlike an enumeration sort, each item does not have to be compared with each of the other items, but instead only with a reduced subset of items already positioned.
Unlike a special-purpose sort defined for specific small groups of items, the inventive process readily generalizes to large numbers of items.
Whereas all previously known sorting procedures have relative strengths and weaknesses dependent on the intended application, the invention does not lose its advantage of minimizing comparisons due to the distribution of the items sorted, nor according to the mechanisms supporting its implementation.
Similar to address table sorting, where link addresses point to successive item locations, the invention creates link addresses that are ordered before rearranging items.
As with keysorting, a unique value is placed with the link addresses for greater speed.
Like with list sorting, an auxiliary link field is included in each record and, for the final result, records are linked in a list of links pointing to the records that follow them.
Unlike address calculation sorting, that merely estimates the general position of each item to accelerate its final placement, the invention fixes the final relative position for each item through a calculated (not random) convergent process.
The number of comparisons among data and the number of data movements necessary are thereby reliably reduced, and generally to a greater extent.
In order to reduce the time required for sorting, Batcher's parallel method performs all indicated comparisons and exchanges by using parallel operations.
Sorting is completed in ½[lg N]([lg N]+1) time-steps (e.g., 55 parallel steps for 1024 items to sort).
Whereas the present invention is not governed by the information theoretic lower bound with respect to each item compared, all other methods are so limited.
Without parallel means, to sort N items, the inventive process requires a maximum number of comparisons equal to the series sum for N terms of ([lg N]+1).
However, once parallel processes are applied to the inventive process, time-steps are saved as well.
The relative positioning of one of plural items can be underway while the search for the position of the next item is initiated.
Thereby, idle areas in the search space, with respect to one path of comparisons, are employed via parallel processing for another path of comparisons, not engaged by the first path; thus, parallel processing in distinct sections of the whole problem space can occur simultaneously.
In the event that plural sequentially ordered items are routed to adjacent regions of space, the final position of one item may be contingent on the final placement of the other.
Even under such conditions, the returned value of the first item placed need not propagate all the way to the root of the search tree.
By employing parallel processes, not precluding serial processing at some stages of operation, the inventive process requirements will approach [lg N]+1 or fewer steps to sort N items, a significant savings.
Radix sorting, also known as distribution sorting, eliminates the need to compare keys directly by representing the keys as b-bit integers.
Sorting proceeds linearly through the entire sorting key associated with each item, in the direction implied by the choice of the beginning digit depends on whether the least or most significant digit is the first chosen.
The keys are sorted one digit at a time and then permuted to their respective locations.
Nonetheless, the radix method of sorting requires many steps, wherein every item or associated key is moved multiple times (a function of the number of digits required for a key to accommodate the number of distinct sorting codes desired).
In general, moving items is more time-consuming than comparing items.
One embodiment of the present invention requires no movement of items, instead pointers are set by comparing N items to be sorted.
In this case, the inventive process establishes a sequential path by following links from one item to another in the sorted order.
None of the applications important for sorting:                collecting items with similar features into sets;        matching items in two or more files; and        searching for information by key values, depend on sorting anything beyond data.        
Data is categorized by common features, prioritized for the purpose of facilitating the logical combination of data from different fields, and then retrieved according to variously ordered indices.
The invention can be used to advantage in the above data-oriented application areas.
In addition, the invention can be used to sort physical tokens, method or system instructions, storage addresses, or transmission and transportation paths.
This means that inventory tracking, the distribution of goods, traffic direction, routing for delivery vehicles, path allocation, computer-aided software engineering, search processes, communication network routing, and applications for pattern recognition processes that lead to tangible outcomes are among the applications that can all benefit from diverse embodiments of the invention.
Unlike other sorting methods that rely solely on virtual representations in order to reduce the number of moves required to complete a sorting, the invention can sort real items in real space and time, therefore the invention can be readily applied to sorting physical tokens with no loss of its relative performance efficiency.
Since anything can be sorted using the invention, customized orderings that have no established a priori sequences are possible.
Concurrent sortings of real-time changing priorities can thus be applied to critical path management.
All publications, including patent documents and texts, referred to in this application are incorporated by reference in their entirety for all purposes to the same extent as if each individual publication were individually incorporated by reference.